package com.michael.skiplist;

import lombok.Getter;
import lombok.Setter;

import java.security.SecureRandom;

@Setter
@Getter
public class SkipList {
    final static SecureRandom secureRandom = new SecureRandom();
    final double RATIO = 0.25;
    final int MAX_LEVEL = 32;
    private SkipListNode header, tail;
    private long length;
    int level;

    public SkipList() {
        level = 1;
        length = 0;
        header = new SkipListNode(null, MAX_LEVEL);
        for (int i = 0; i < MAX_LEVEL; i++) {
            header.getLevel()[i].setForward(null);
            header.getLevel()[i].setSpan(0);
        }
        header.setBackward(null);
        tail = null;
    }

    public boolean search(int target) {
        SkipListNode current = header;
        //先从最高层遍历
        for (int i = this.level - 1; i >= 0; i--) {
            while (current.getLevel()[i].getForward() != null) {
                if (current.getLevel()[i].getForward().getObj().compareTo(target) < 0) {
                    current = current.getLevel()[i].getForward();
                }else if(current.getLevel()[i].getForward().getObj().compareTo(target) == 0){
                    return true;
                }else{
                    break;
                }
            }
        }
        return false;
    }

    public void add(int obj) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL];
        SkipListNode current = header;
        int[] rank = new int[MAX_LEVEL];
        //先从最高层遍历
        for (int i = this.level - 1; i >= 0; i--) {
            rank[i] = (i == this.level - 1) ? 0 : rank[i + 1];
            while (current.getLevel()[i].getForward() != null && current.getLevel()[i].getForward().getObj().compareTo(obj) < 0) {
                // 记录沿途跨越了多少个节点
                rank[i] += current.getLevel()[i].getSpan();
                current = current.getLevel()[i].getForward();
            }
            update[i] = current;
        }
        int level = randomLevel();
        if (this.level < level) {
            //初始化未使用层
            for (int i = this.level; i < level; i++) {
                rank[i] = 0;
                update[i] = header;
                update[i].getLevel()[i].setSpan((int) this.length);
            }
            this.level = level;
        }
        //创建新节点
        current = new SkipListNode(obj, level);
        // 将前面记录的指针指向新节点，并做相应的设置
        for (int i = 0; i < level; i++) {
            current.getLevel()[i].setForward(update[i].getLevel()[i].getForward());
            // 将沿途记录的各个节点的 forward 指针指向新节点
            update[i].getLevel()[i].setForward(current);

            /* update span covered by update[i] as x is inserted here */
            // 计算新节点跨越的节点数量
            current.getLevel()[i].setSpan(update[i].getLevel()[i].getSpan() - (rank[0] - rank[i]));

            // 更新新节点插入之后，沿途节点的 span 值
            // 其中的 +1 计算的是新节点
            update[i].getLevel()[i].setSpan(rank[0] - rank[i] + 1);
        }
        // 未接触的节点的 span 值也需要增一，这些节点直接从表头指向新节点
        // T = O(1)
        for (int i = level; i < this.level; i++) {
            update[i].getLevel()[i].incrSpan();
        }
        // 设置新节点的后退指针
        current.setBackward((update[0] == header) ? null : update[0]);
        if (current.getLevel()[0].getForward() != null)
            current.getLevel()[0].getForward().setBackward(current);
        else
            tail = current;

        // 跳跃表的节点计数增一
        length++;
    }

    private int randomLevel() {
        int level = 1;

        while ((secureRandom.nextInt() & 0xFFFF) < (RATIO * 0xFFFF))
            level += 1;

        return (level < MAX_LEVEL) ? level : MAX_LEVEL;
    }

    public boolean erase(int obj) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL];
        SkipListNode current = header;

        //遍历跳跃表，查找目标节点，并记录所有沿途节点
        for (int i = this.level - 1; i >= 0; i--) {
            // 遍历跳跃表的复杂度为
            while (current.getLevel()[i].getForward() != null &&
                    current.getLevel()[i].getForward().getObj().compareTo(obj) < 0) {

                // 沿着前进指针移动
                current = current.getLevel()[i].getForward();
            }
            // 记录沿途节点
            update[i] = current;
        }
        //检查找到的元素 x ，只有在它的分值和对象都相同时，才将它删除。
        current = current.getLevel()[0].getForward();
        if (current != null && current.getObj().compareTo(obj) == 0) {
            // T = O(1)
            deleteNode(current, update);
            // T = O(1)
            return true;
        } else {
            return false; /* not found */
        }
    }

    private void deleteNode(SkipListNode current, SkipListNode[] update) {
        for (int i = 0; i < this.level; i++) {
            if (update[i].getLevel()[i].getForward() == current) {
                update[i].getLevel()[i].setSpan(current.getLevel()[i].getSpan() - 1);
                update[i].getLevel()[i].setForward(current.getLevel()[i].getForward());
            } else {
                update[i].getLevel()[i].decrSpan();
            }
        }

        // 更新被删除节点 x 的前进和后退指针
        if (current.getLevel()[0].getForward() != null) {
            current.getLevel()[0].getForward().setBackward(current.getBackward());
        } else {
            this.tail = current.getBackward();
        }

        // 更新跳跃表最大层数（只在被删除节点是跳跃表中最高的节点时才执行）
        // T = O(1)
        while (level > 1 && header.getLevel()[this.level - 1].getForward() == null)
            this.level--;

        // 跳跃表节点计数器减一
        this.length--;
    }
}
